/**
//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 
//
// 你可以按 任何顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
//
// 示例 2： 
//
// 
//输入：n = 1, k = 1
//输出：[[1]] 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 1 <= k <= n 
// 
// Related Topics 数组 回溯 👍 940 👎 0

*/

package com.xixi.basicAlgroithms.backtracking;

import java.util.ArrayList;
import java.util.List;

public class ID00077Combinations {
public static void main(String[] args) {

    Solution solution = new ID00077Combinations().new Solution();
    System.out.println(solution.combine(5,3));


}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    //结果集
    public List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {

        //生成一个从1到n的数组
        int[] nArray = new int[n];
        for(int i = 0; i < n; ++i){
            nArray[i] = i+1;
        }

        //采用回溯来遍历所有的组合
        backTrack(nArray, n, k, 0, 0, new ArrayList<>());


        return result;

    }


    public void backTrack (int[] nArray, int n , int k, int startPoint, int kindex, List<Integer> path){
        //判断递归终止条件

        //位数够了，返回一个结果快照
        if( kindex == k  ){
            result.add(new ArrayList<>(path));
            return;
        }


        //每个数字递归
        //从每一个数字开始向后，枚举所有数字，如果枚举的数字小于k - （kindex + 1），说明后面的数字不够枚举了（剪枝） n - (k - kindex ) + 1
        for(int i = startPoint; i < n - (k - (kindex +1)); ++i ){
            path.add(nArray[i]); //路径中增加节点
            backTrack(nArray,n,k,i+1, kindex + 1, path);//往下一层递归
            path.remove(kindex);//清掉路径
        }



    }

}
//leetcode submit region end(Prohibit modification and deletion)




}